/**
 * 动态规划，dp规则：相同时取dp[i-1][j-1]，不同时，取删除word1的i后或者删除word2的j后的最小值+1
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    let len1 = word1.length,
        len2 = word2.length,
        dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0));
    for(let i = 0;i<=len1;i++){
        dp[i][0] = i
    }
    for(let j = 0;j<=len2;j++){
        dp[0][j] = j
    }

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if(word1[i-1] === word2[j-1]){
                dp[i][j] = dp[i-1][j-1]
            }else{
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + 1
            }
        }
    }

    return dp[len1][len2]
};